/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

#include <stack>
using namespace std;
class Solution {
    stack<pair<TreeNode*,int> > s;
    vector<int> ans;
    enum visit_type {self, left, right};
public:
    vector<int> postorderTraversal(TreeNode *root) {
        while (!s.empty()) s.pop();
        ans.clear();
        if (root==NULL) return ans;
        s.push(make_pair(root,self));
        while (!s.empty()) {
            if (s.top().second==self) {
                s.top().second=left;
                if (s.top().first->left!=NULL) {
                    s.push(make_pair(s.top().first->left, self));
                    continue;
                }
            }
            if (s.top().second==left) {
                s.top().second=right;
                if (s.top().first->right!=NULL) {
                    s.push(make_pair(s.top().first->right, self));
                    continue;
                }
            }
            ans.push_back(s.top().first->val);
            s.pop();
        }
        return ans;
    }
};
